A Field Guide to Genetic Programming by Riccardo Poli & William B Langdon & Nicholas F. McPhee

Author:Riccardo Poli & William B Langdon & Nicholas F. McPhee [Poli, Riccardo]
Language: eng
Format: epub
ISBN: 9781447533115
Publisher: Lulu.com
Published: 2011-06-19T16:00:00+00:00

12.11 Compression

Koza (1992) was the first to use genetic programming to perform compression. He considered, in particular, the lossy compression of images. The idea was to treat an image as a function of two variables (the row and column of each pixel) and to use GP to evolve a function that matches as closely as possible the original. One can then use the evolved GP tree as a lossy compressed version of the image, since it is possible to obtain the original image by evaluating the program at each row-column pair of interest. The technique, which was termed programmatic compression, was tested on one small synthetic image with good success. Programmatic compression was further developed and applied to realistic data (images and sounds) by Nordin and Banzhaf (1996).

Iterated Functions System (IFS) are important in the domain of fractals and the fractal compression algorithm. Lutton, Levy-Vehel, Cretin, Glevarec, and Roll (1995a,b) used genetic programming to solve the inverse problem of identifying a mixed IFS whose attractor is a specific binary (black and white) image of interest. The evolved program can then be taken to represent the original image. In principle, this can then be further compressed. The technique is lossy, since rarely the inverse problem can be solved exactly. No practical application or compression ratio results were reported in (Lutton et al., 1995a,b). Using similar principles, Sarafopoulos (1999) used GP to evolve affine IFSs whose attractors represent a binary image containing a square (which was compressed exactly) and one containing a fern (which was achieved with some error in the finer details).

Wavelets are frequently used in lossy image and signal compression. Klappenecker and May (1995) used GP to evolve wavelet compression algorithms (internal nodes represented conjugate quadrature filters, leaves represented quantisers). Results on a small set of real-world images were impressive, with the GP compression outperforming JPEG at all compression ratios.

The first lossless compression technique (Fukunaga and Stechert, 1998) used GP to evolve non-linear predictors for images. These were used to predict the gray level a pixel will take based on the gray values of a subset of its neighbours (those that have already been computed in a row-by-row and column-by-column scan of the image array). The prediction errors together with the model’s description represent a compressed version of the image. These were compressed using the Huffman encoding. Results on five images from the NASA Galileo Mission database were very promising with GP compression outperforming some of the best human-designed lossless compression algorithms.

In many compression algorithms some form of pre-processing or transformation of the original data is performed before compression. This often improves compression ratios. Parent and Nowe (2002) evolved pre-processors for image compression using GP. The objective of the pre-processor was to reduce losslessly the entropy in the original image. In tests with five images from the Canterbury corpus, GP was successful in significantly reducing the image entropy. As verified via the application of bzip2, the resulting images were markedly easier to compress.

In (Krantz, Lindberg, Thorburn, and Nordin, 2002) the use of programmatic compression was extended from images to natural videos.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.